Ch.1 Propositions and Truth Tables

Definitions

Proposition: statement that is always True or False (but not both)

Notation: $p,q,r,s...$

Theorem: a proposition that are always True, but is not direct to check

Connectors

Negation: $\neg$ reverse True/False value
AND: $\land$
OR: $\lor$
Conditional statement: $\implies$
Connecting two propositions gives a new proposition

Truth Table

$p$	$q$	$\lor p$	$p\land q$	$p\implies q$	$\lnot(p\implies q)$	$p\land\lnot q$
$T$	$T$	$F$	$T$	$T$	$F$	$F$
$T$	$F$	$F$	$F$	$F$	$T$	$T$
$F$	$T$	$T$	$F$	$T$	$F$	$F$
$F$	$F$	$T$	$F$	$T$	$F$	$F$

Quantifiers

Statement $x>3$ is not a proposition
Statement $\text{For all real numbers }x, x+1>x$ is a proposition
Statement $\text{There exists a pair of irrational numbers }x,y\text{ such that }x^y\text{ is rational}$ is a proposition
"For all" $\forall$ , "There exists" $\exists$ quantifies domain

English	Desc	Math
For all real numbers $x$ , $x+1>x$	Above can be represented as $P(x)$ , where $P$ is the property checked ( $x+1>x$ ) and $x$ is the dependence.	Mathematically, $\forall xP(x),$ where $x\in\mathbb{R}$
There exists a pair of irrational numbers $x,y$ s.t. $x^y$ is rational.	This is $P(x,y)$ , where $P$ is property, $x^y$ is rational, and $x,y$ are the dependences.	Mathematically, $\exists x,yP(x,y)$ , where $x,y\in\mathbb{R}\setminus\mathbb{Q}$

Propositional Functions

not a proposition; depends on variable(s)
As soon as a value is assigned to the variables, the statement becomes a proposition
" $x>3$ " denoted $xP(x)$ , where $P(x)=$ " $x>3$ "

Other Propositions

Converse: $q\implies p$
Inverse: $\lnot p\implies \lnot q$
Contrapositive: $\lnot q\implies\lnot p$

$p$	$q$	$p\implies q$	$\lnot q\implies\lnot p$
$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$
$F$	$T$	$T$	$T$
$F$	$F$	$T$	$T$

A proposition is equivalent to its contrapositive; i.e. $p\implies q$ can be proven by proving $\lnot q\implies\lnot p\rightarrow$ Proof by Contrapositive (details in Ch.2)

Example 1.1 Propositional Functions

If a natural number $x$ is greater than one, then $x$ is even
This is a propositional function
$xP(x)$ where $x\in\mathbb{N}$ and $P(x)=$ "is greater than one"
$xQ(x)$ where $x\in\mathbb{N}$ and $Q(x)=$ "is even"
Combine to
$x(P(x)\implies Q(x))$ where $x\in\mathbb{N}$
If $x=2$ , the statement is true.
If $x=5$ , the statement is false.
If $x=1$ , the statement is true due to $F\implies F$ .

Note: if this was $\forall x\in\mathbb{N}\setminus\{1\}$ $x$ is even, it would be a false proposition- more specifically, a false quantifier

$x(P(x)\implies Q(x))$ is equivalent to $x(P\land\lnot Q)$
This is equivalent to $\lnot(P\land\lnot Q)=\lnot P\lor Q$ , or in the case above, $x(\lnot P(x)\lor Q(x))$

De Morgan's Laws

$\lnot(p\land q)=\lnot p\lor\lnot q$
$\lnot(p\lor q)=\lnot p\land\lnot q$
$\lnot(\forall xP(x))=\exists x(\lnot P(x))$
$\lnot(\exists xP(x))=\forall x(\lnot P(x))$

Arguments

bunch of statements, and a conclusion
$P_1,P_2,\cdots,P_k\therefore t\equiv(P_1\land P_2\land\cdots\land P_k)\implies t$

(p\implies q)\land(q\implies r)\implies(p\implies r)

Premises, $p\implies q$ and $q\implies r$ , are assumed to be true.

$p$	$q$	$r$	$p\implies q$	$q\implies r$	$p\implies r$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$T$	$F$	$T$	$F$
$T$	$F$	$T$	$F$	$T$
$T$	$F$	$F$	$F$	$T$
$F$	$T$	$T$
$F$	$T$	$F$
$F$	$F$	$T$
$F$	$F$	$F$

Operator Precedence Chart

Operator	Precedence
$\lnot$	1
$\land$	2
$\lor$	3
$\implies$	4
$\iff$	5

$p$	$q$	$\lor p$	$p\land q$	$p\implies q$	$\lnot(p\implies q)$	$p\land\lnot q$
$T$	$T$	$F$	$T$	$T$	$F$	$F$
$T$	$F$	$F$	$F$	$F$	$T$	$T$
$F$	$T$	$T$	$F$	$T$	$F$	$F$
$F$	$F$	$T$	$F$	$T$	$F$	$F$

$p$	$q$	$r$	$p\implies q$	$q\implies r$	$p\implies r$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$T$	$F$	$T$	$F$
$T$	$F$	$T$	$F$	$T$
$T$	$F$	$F$	$F$	$T$
$F$	$T$	$T$
$F$	$T$	$F$
$F$	$F$	$T$
$F$	$F$	$F$

$p$	$q$	$\lor p$	$p\land q$	$p\implies q$	$\lnot(p\implies q)$	$p\land\lnot q$
$T$	$T$	$F$	$T$	$T$	$F$	$F$
$T$	$F$	$F$	$F$	$F$	$T$	$T$
$F$	$T$	$T$	$F$	$T$	$F$	$F$
$F$	$F$	$T$	$F$	$T$	$F$	$F$

$p$	$q$	$r$	$p\implies q$	$q\implies r$	$p\implies r$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$T$	$F$	$T$	$F$
$T$	$F$	$T$	$F$	$T$
$T$	$F$	$F$	$F$	$T$
$F$	$T$	$T$
$F$	$T$	$F$
$F$	$F$	$T$
$F$	$F$	$F$

$p$	$q$	$\lor p$	$p\land q$	$p\implies q$	$\lnot(p\implies q)$	$p\land\lnot q$
$T$	$T$	$F$	$T$	$T$	$F$	$F$
$T$	$F$	$F$	$F$	$F$	$T$	$T$
$F$	$T$	$T$	$F$	$T$	$F$	$F$
$F$	$F$	$T$	$F$	$T$	$F$	$F$

$p$	$q$	$r$	$p\implies q$	$q\implies r$	$p\implies r$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$T$	$F$	$T$	$F$
$T$	$F$	$T$	$F$	$T$
$T$	$F$	$F$	$F$	$T$
$F$	$T$	$T$
$F$	$T$	$F$
$F$	$F$	$T$
$F$	$F$	$F$